/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package item11;

import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:SortArrFindMin.java v1.0 2018/7/14 下午3:24 LvJing Exp $
 */
public class SortArrFindMin {

    /**
     * 面试题11：找出旋转数组的最小数字：对一个递增数组进行旋转，如1，2，3，4，5旋转为3，4，5，1，2，找出旋转后数组中最小的数字。
     * 思路：找出数组中最小的数字，这里显然不能直接使用全局遍历，要利用数组的递增特点，考虑到该特点，在数组旋转过后可以看出，前子数组的最小数字
     * 是大于后子数组的最大数字的，所以可以利用二分法思想，开始和结尾设一个指针，判断中间元素的值，如果大于开始指针的值（前子数组最小值），则
     * 数组的最小值在中间元素后面，如果小于结束指针的值（后子数组最大数字），则数组最小值位于中间元素前面。
     * 但是，递增间距为0的数组也叫递增，即0，1，1，1，1，这时它旋转后可能是1，1，1，0，1，显然无法再通过数组的值进行比较，所以这种情况下，
     * 只能手动全局遍历数组找到最小值
     */
    private class Solution {

        private int minNumberInRotateArray(int[] array) {
            if (array == null || array.length <= 0) {
                return -1;
            }
            if (array.length == 1) {
                return array[0];
            }

            int startIndex = 0;
            int endIndex = array.length - 1;
            int midIndex = 0;
            while (array[startIndex] >= array[endIndex]) {
                // 前角标与后角标相邻，后角标就是最小元素
                if (endIndex - startIndex == 1) {
                    midIndex = endIndex;
                    break;
                }

                // 如果前后角标、中间元素都相等，证明这个数组是递增值为0的，只能手动全局排序查找
                if (array[startIndex] == array[endIndex] && array[startIndex] == array[midIndex]) {
                    return findMin(array);
                }

                midIndex = (startIndex + endIndex) / 2;
                if (array[midIndex] >= array[startIndex]) {
                    // 比前子数组的第一个数大，则最小数在中间元素后面
                    startIndex = midIndex;
                } else if (array[midIndex] <= array[endIndex]) {
                    // 比后子数组的最后一个数小，则最小数在中间元素前面
                    endIndex = midIndex;
                }
            }

            return array[midIndex];
        }

        private int findMin(int[] array) {
            int min = array[0];
            for (int i = 1; i < array.length; i++) {
                if (min > array[i]) {
                    min = array[i];
                    break;
                }
            }
            return min;
        }
    }

    private Solution solution;

    @Before
    public void init() {
        solution = new Solution();
    }

    /**
     * 特殊输入测试，输入null
     */
    @Test
    public void test01() {
        Assert.assertEquals(-1, solution.minNumberInRotateArray(null));
        Assert.assertEquals(-1, solution.minNumberInRotateArray(new int[0]));
    }

    /**
     * 边界值测试，输入的数组是一个递增排序的数组，但是只包含一个数字
     */
    @Test
    public void test02() {
        Assert.assertEquals(1, solution.minNumberInRotateArray(new int[] { 1, 1, 1, 1 }));
        Assert.assertEquals(0, solution.minNumberInRotateArray(new int[] { 1, 1, 1, 0, 1, 1 }));
    }

    /**
     * 功能性测试：输入的数组是一个升序排列后旋转的数组，数组中没有重复数字
     */
    @Test
    public void test03() {
        Assert.assertEquals(1, solution.minNumberInRotateArray(new int[] { 3, 4, 5, 1, 2 }));
    }

    /**
     * 功能性测试：输入的数组是一个升序排列后旋转的数组，数组中有重复数字
     */
    @Test
    public void test04() {
        Assert.assertEquals(1, solution.minNumberInRotateArray(new int[] { 3, 4, 5, 6, 1, 1, 2, 2 }));
    }
}
